package sorting;

public class InsertionSort {

	public static <T extends Comparable<? super T>> void sort(T[] data) {

		for (int maxIndex = 0; maxIndex < data.length; maxIndex++) {
			for (int currentIndex = maxIndex; currentIndex > 0; currentIndex--) {
				if (data[currentIndex-1].compareTo(data[currentIndex]) > 0) {
					T element = data[currentIndex];
					data[currentIndex] = data[currentIndex-1];
					data[currentIndex-1] = element;
				} else {
					break;
				}
			}
		}
	}

	public static <T extends Comparable<? super T>> void sort2(T[] data) {

		for (int index = 1; index < data.length; index++) {
			T key = data[index];
			int position = index;

			while (position > 0 && data[position-1].compareTo(key) > 0) {
				data[position] = data[position-1];
				position--;
			}
			data[position] = key;
		}
	}
}
